//给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//
// candidates 中的每个数字在每个组合中只能使用 一次 。
//
// 注意：解集不能包含重复的组合。
//
//
//
// 示例 1:
//
//
//输入: candidates = [10,1,2,7,6,1,5], target = 8,
//输出:
//[
//[1,1,6],
//[1,2,5],
//[1,7],
//[2,6]
//]
//
// 示例 2:
//
//
//输入: candidates = [2,5,2,1,2], target = 5,
//输出:
//[
//[1,2,2],
//[5]
//]
//
//
//
// 提示:
//
//
// 1 <= candidates.length <= 100
// 1 <= candidates[i] <= 50
// 1 <= target <= 30
//
//
// Related Topics 数组与矩阵 回溯与递归 👍 1335 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function combinationSum2(candidates: number[], target: number): number[][] {

    function backtracking(sum, temp, startIndex) {

        if (sum > target) return;
        if (sum === target) {
            res.push(temp.slice())
            return;
        }
        //? 那么这个又该怎么去重呢？首先需要sort，然后判断
        for (let i = startIndex; i < candidates.length; i ++) {
            //? 精髓在于i > startIndex!这让此判断必然不在同一轮中生效(在同一个递归轮次中i始终等于startIndex)
            if (i > startIndex && candidates[i] === candidates[i - 1]) continue
            temp.push(candidates[i])
            backtracking(sum + candidates[i], temp,i + 1)
            temp.pop()
        }
    }
    let res : number[][] = []
    candidates.sort((a, b) => a - b)
    backtracking(0,[],0)
    return res
};
//leetcode submit region end(Prohibit modification and deletion)
